package three_shang.智能算法;

import java.util.Arrays;
import java.util.Random;

public class SAK {


    // 物品重量
    private static final int[] weights = {2, 3, 5, 1, 4};
    // 物品价值
    private static final int[] values = {2, 5, 8, 3, 6};
    // 背包容量
    private static final int capacity = 8;
    // 物品个数
    private static final int n = weights.length;
    // 温度衰减率
    private static final double coolingRate = 0.95;
    // 初始温度
    private static final double initialTemp = 1000;
    // 终止温度
    private static final double finalTemp = 1;

    public static void main(String[] args) {
        int[] bestSolution = simulatedAnnealing();
        printSolution(bestSolution);
    }

    // 计算当前背包的总价值
    public static int getTotalValue(int[] solution) {
        int totalValue = 0;
        int totalWeight = 0;
        for (int i = 0; i < n; i++) {
            if (solution[i] == 1) {
                totalWeight += weights[i];
                totalValue += values[i];
            }
        }
        // 如果超过容量则返回0
        return totalWeight > capacity ? 0 : totalValue;
    }

    // 随机生成一个邻域解
    public static int[] getNeighbor(int[] currentSolution) {
        Random random = new Random();
        int[] neighbor = Arrays.copyOf(currentSolution, currentSolution.length);
        // 随机选择一个物品，改变它的选取状态（0变1或1变0）
        int index = random.nextInt(n);
        neighbor[index] = 1 - neighbor[index];
        return neighbor;
    }

    // 模拟退火算法
    public static int[] simulatedAnnealing() {
        Random random = new Random();
        // 初始解
        int[] currentSolution = new int[n];
        // 随机生成一个初始解
        for (int i = 0; i < n; i++) {
            currentSolution[i] = random.nextBoolean() ? 1 : 0;
        }

        int[] bestSolution = Arrays.copyOf(currentSolution, n);
        int bestValue = getTotalValue(bestSolution);

        double temp = initialTemp;

        // 模拟退火过程
        while (temp > finalTemp) {
            // 生成邻域解
            int[] neighbor = getNeighbor(currentSolution);
            int currentValue = getTotalValue(currentSolution);
            int neighborValue = getTotalValue(neighbor);

            // 如果邻域解更优，接受它
            if (neighborValue > currentValue) {
                currentSolution = neighbor;
            } else {
                // 否则，以一定概率接受劣解
                double acceptanceProbability = Math.exp((neighborValue - currentValue) / temp);
                if (random.nextDouble() < acceptanceProbability) {
                    currentSolution = neighbor;
                }
            }

            // 更新最优解
            if (getTotalValue(currentSolution) > bestValue) {
                bestSolution = Arrays.copyOf(currentSolution, n);
                bestValue = getTotalValue(bestSolution);
            }

            // 降低温度
            temp *= coolingRate;
        }

        return bestSolution;
    }

    // 输出解的详细信息
    public static void printSolution(int[] solution) {
        System.out.println("选中的物品为:");
        int totalWeight = 0;
        int totalValue = 0;
        for (int i = 0; i < solution.length; i++) {
            
            if (solution[i] == 1) {
                System.out.println("物品: " + (i + 1) + " 重量: " + weights[i] + "     ----------------->     价值: " + values[i]);
                totalWeight += weights[i];
                totalValue += values[i];
            }
        }
        System.out.println("Total Wight: " + totalWeight);
        System.out.println("Total Value: " + totalValue);
    }


}